package a_doubleWrite;

/**
 * 149. 直线上最多的点数
 * 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。
 * 求最多有多少个点在同一条直线上。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-28 17:42
 */
public class L149 {
    /**
     * 每次枚举三个节点，两两判断斜率是否相等
     *
     * @param points 点数组
     * @return int
     */
    public int maxPoints(int[][] points) {
        if (points == null || points.length == 0) return 0;
        if (points.length == 1) return 1;
        int max = 0;
        int len = points.length;
        for (int i = 0; i < len; i++) {
            int[] a = points[i];
            for (int j = i + 1; j < len; j++) {
                int[] b = points[j];
                int count = 2;//两点一定可以确定一直线
                for (int k = j + 1; k < len; k++) {
                    int[] c = points[k];
                    //不能使用除法，可能除以0
                    //判断交叉相乘是否相等
                    int x = (a[0] - b[0]) * (a[1] - c[1]);
                    int y = (a[0] - c[0]) * (a[1] - b[1]);
                    if (x == y) count++;
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}
